package com.example.zzy.zzytest.algo.sort.nlognsort;

/**
 * 快排
 * 通过一趟排序，将数组分成三块，1.第一个元素，也是切分元素 2.比切分元素小的部分 3.比切分元素大的部分
 *
 * 1.第一个元素做切分
 * 2.左指针找大的，右指针找小的，找到就交换位置，左右两指针相遇时结束
 * 3.将切分元素放进正确的位置
 */
public class QuickSort {
    private static void sort(int[] arr, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int j = partition(arr, lo, hi);
        sort(arr, lo, j - 1);
        sort(arr, j + 1, hi);
    }

    private static int partition(int[] a, int lo, int hi) {
        int i = lo, j = hi + 1;//左右指针
        int v = a[lo];//切分元素
        while (true) {
            //左指针找到大于切分元素的值，右指针找到小于切分元素的值
            while (++i <= hi && a[i] < v) ;
            while (--j >= lo && a[j] > v) ;

            if (i >= j) {
                break;
            }
            exch(a, i, j);
        }
        //将切分元素放进正确的位置
        exch(a, lo, j);
        return j;
    }

    private static void exch(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] testArr = new int[]{-9, 78, 0, 23, -567, 70};
        sort(testArr, 0, 5);
    }
}
